package 我的Java学习_算法基础.day_07;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2021/8/20 - 08 - 20 - 11:14
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _110_子集生成之二进制法 {
    public static void main(String[] args) {
        int[] a = {3,2,1};
        ArrayList<ArrayList<Integer>> t = getSubsets(a);
        System.out.println(t);
    }
    private static ArrayList<ArrayList<Integer>> getSubsets(int[] a){
        int length = a.length;
        Arrays.sort(a);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();//大集合
        //[[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
        for(int i = 0;i<(int)Math.pow(2,length);i++){
            ArrayList<Integer> s = new ArrayList<>();
            for(int j =0;j<length;j++){
                if(((i>>j)&1)==1){
                    s.add(a[j]);
                }
            }
            res.add(s);
        }
        return res;
    }
}

//[[1, 2, 3], [2, 3], [1, 3], [3], [1, 2], [2], [1]]
//        for(int i = (int)Math.pow(2,length)-1;i>0;i--){//大数字-1
//            ArrayList<Integer> s = new ArrayList<>();//对每个i建立一个集合
//            for(int j =0;j<length;j++){
//                if(((i>>j)&1)==1){
//                    s.add(a[j]);
//                }
//            }
//            res.add(s);
//        }




//[[3, 2, 1], [3, 2], [3, 1], [3], [2, 1], [2], [1]]
//        for(int i = (int)Math.pow(2,length)-1;i>0;i--){//大数字-1
//            ArrayList<Integer> s = new ArrayList<>();//对每个i建立一个集合
//            for(int j = length-1;j>=0;j--){//检查哪个位上的二进制为1,从高位开始检查，高位对应着数组靠后的元素
//                if(((i>>j)&1)==1){
//                    s.add(a[j]);
//                }
//            }
//            res.add(s);
//        }
